package 剑指Offer._5160;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/15 16:37
 * 在排序数组中查找数字 I
 * 统计一个数字在排序数组中出现的次数。
 * 算法：二分查找
 * 一般排序数组，就用二分
 * 找到 target 所在的左区间和右区间，相减得到结果
 */
public class _53I {
    public static void main(String[] args) {
        System.out.println(new _53I().search_perfect(new int[]{1}, 1));
    }

    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int ans = 0;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) ++ans;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return ans;
    }

    public int search_perfect(int[] nums, int target) {
        return binarySearch(nums, target) - binarySearch(nums, target - 1);
    }
    int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        // [1] 1
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] <= target) l = mid + 1;
            else r = mid - 1;
        }
        System.out.println(l);
        return l;
    }

}
